#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdlib.h>

void GetNext(char* sub, int* next, int len)
{
    next[0] = -1;
    next[1] = 0;
    int k = 0;
    int i = 2;
    while(i < len)
    {
        if(k == -1 || sub[i - 1] == sub[k])
        {
            next[i] = k + 1;
            i++;
            k++;
        }
        else
        {
            k = next[k];
        }
    }
}

int KMP(char* str, char* sub, int pos)
{
    //处理边界情况
    assert(str != NULL && sub != NULL);
    int lenStr = strlen(str);
    int lenSub = strlen(sub);
    if(lenStr == 0 || lenSub == 0)
        return -1;
    if(pos < 0 || pos >= lenStr)
        return -1;
    
    //创建next数组
    int* next = (int*)malloc(sizeof(int) * lenSub);
    assert(next != NULL);
    GetNext(sub, next, lenSub);
    
    int i = pos; //主串
    int j = 0;   //子串
    
    while (i < lenStr && j < lenSub)
    {
        if(j == -1 || str[i] == sub[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    
    free(next);
    
    if(j >= lenSub)
        return i - j;
    
    return -1;
}

int main()
{
    printf("%d\n",KMP("abcdaabbe","aa",0));
    printf("%d\n",KMP("abcdaabbe","ac",0));
    printf("%d\n",KMP("abcdaabbe","abc",0));
    return 0;
}

